package com.xhq.test.springboot.springbootdemo.leetcode;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * @author huiny
 * @since 2021/6/8 23:03
 */
public class SubStringMaxOccur {


 /*
    给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：

子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。

示例 1：
输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

示例 2：
输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

示例 3：
输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

示例 4：
输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出：0
 
提示：
1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s 只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


    @Test
    void run() {

        var a = maxFreq("aababcaab",
                2,
                3,
                4);
        Assertions.assertEquals(2, a);

        a = maxFreq("aaaa",
                1,
                3,
                3);
        Assertions.assertEquals(2, a);

        a = maxFreq("aabcabcab",
                2,
                2,
                3);
        Assertions.assertEquals(3, a);

        a = maxFreq("abcde",
                2,
                3,
                3);
        Assertions.assertEquals(0, a);
    }

    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        if(s == null || s.trim().length() == 0 || maxSize < minSize
                || maxLetters < 1 || minSize < 1 || s.length() < minSize) {
            return 0;
        }

        int typeSum = countType(s);
        HashMap<String, Integer> individualCount = new HashMap<>();
        for(int i = 0; i < s.length() - minSize + 1; i++) {
            var subStr = s.substring(i, i+minSize);
            boolean isGreateMaxLetters = (typeSum > maxLetters) && (countType(subStr) > maxLetters);
            if(isGreateMaxLetters) {
                continue;
            }
            Integer val = individualCount.get(subStr);
            individualCount.put(subStr, val == null ? 1 : ++val);
            // "abc" 肯定会覆盖 a, ab, 即长的肯定会覆盖短的,只要考虑最短的就好咯. 最短字符串出现的次数>=长字符串出现次数
            /*for(int k = 0; k < segmentCount; k ++) {
                int end = i + minSize + k;
                if(end > s.length()) {
                    break;
                }
                var subStr = s.substring(i, end);
                boolean isGreateMaxLetters = (typeSum > maxLetters) && (countType(subStr) > maxLetters);
                if(isGreateMaxLetters) {
                    continue;
                }
                Integer val = individualCount.get(subStr);
                individualCount.put(subStr, val == null ? 1 : ++val);
            }*/
        }

        var result = individualCount.values().stream().max(Integer::compareTo);
        return result.orElse(0);
    }

    private int countType(String s) {
        char[] charArray = s.toCharArray();
        int[] charCount = new int[26];
        for(int i=0; i < charArray.length; i++) {
            charCount[charArray[i] - 'a']++;
        }
        int typeCount =0;
        for(int i = 0; i < charCount.length; i ++) {
            if(charCount[i] > 0) {
                typeCount++;
            }
        }
        return typeCount;
    }
}
